package com.demo.data.struct2.排序;

/**选择排序：每轮选择出最小的元素，和未排序的最左边元素交换，即第一轮和第0个交换；第二轮和第1个交换...
 * 当集合有序度高的时候，没有冒泡效率高，因为冒泡可以优化省略有序后的多轮处理；选择则不可以
 * @author HP
 *
 */
public class SelectSort {

	public static void main(String[] args) {
		int[] arr = {5,3,7,2,1,9,8,4};
		// 1,3,7,2,5,9,8,4
		// 1,2,7,3,5,9,8,4
		// 1,2,3,7,5,9,8,4
		// 1,2,3,4,5,9,8,7
		// 1,2,3,4,5,9,8,7
		// 1,2,3,4,5,7,8,9
		// 1,2,3,4,5,7,8,9
		Util.display(selection(arr));
	}
	
	private static int[] selection(int[] a) {
		for(int i=0; i<a.length-1; i++) {
			// i: 代表每轮选择最小元素要交换到的目标索引
			int s = i; // 代表每轮找到的最小元素的索引
			for(int j=s+1; j<a.length; j++) {
				if(a[s] > a[j]) {
					s = j;
				}
			}
			if(s != i) {
				Util.swap(a, s, i);
			}
		}
		return a;
	}
	
}
